#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> ret;
        int n = nums.size();

       //1.排序优化
       sort(nums.begin(),nums.end());

       //2.利用双指针解决
       for(int i = 0; i < n;)//先固定一个数
       {
            if(nums[i] > 0) break;//排序完后若固定的数大于0，则不可能符合条件
            //双指针找
            int left = i + 1,right = n -1, a = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum < a) left++;
                else if(sum > a)right--;
                else
                {
                    ret.push_back({nums[i],nums[left++],nums[right--]});
                    //去重left && right(越界)
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1])right--;
                }
            }
            //去重 i 
            i++;
            while(i < n && nums[i] == nums[i - 1]) i++;
       }
       return ret;
    }
};